package LeetCode;

import java.io.InputStream;
import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}14:06
 */
public class M4 {//机器人寻路
    public static int count = 0;
    public static void main(String[] args) {
        M4 m4 = new M4();
        int a = m4.movingCount(3,2,17);
//        for (int i = 0; i < arr.length; i++){
//            for (int j = 0; j < arr[i].length ; j++){
//                System.out.print(arr[i][j]+"  ");
//            }
//            System.out.println();
//        }
        System.out.println(a);
    }

    public  int movingCount(int m, int n, int k) {
        int[][] Road = new int[m][n];
        getRoad(Road,0,0,k);
        return count;
        }


    //回溯法的方法

    /**
     *
     * @param arr
     * @param i
     * @param j
     * @return
     */
    public static boolean getRoad(int[][] arr, int i, int j,int k){
       if (i < 0||j < 0|| i >= arr.length|| j >= arr[i].length || arr[i][j] == -1 || arr[i][j] == 1){
            return false;
       }else if ((i / 10 + i % 10 + j /10 + j %10)>k){
           return false;
       }else {//达到条件可以继续；浪
           count++;
           arr[i][j] = 1;
           boolean index = getRoad(arr,i+1,j,k)
           ||getRoad(arr,i-1,j,k)
           ||getRoad(arr,i,j+1,k)
           ||getRoad(arr,i,j-1,k);
           return index;
       }
    }
}
